|
| creator |
Heljanko, Keijo
| | Stefanescu, Alin
| | date |
2004-10
| | | | description |
37 pages
| |
We consider the distributed implementability problem as: Given a
labeled transition system TS together with a distribution D of its
actions over a set of processes, does there exist a distributed
system over D such that its global transition system is
equivalent' to TS? We consider the distributed system models
of synchronous products of transition systems and Zielonka's
asynchronous automata. In this paper we provide complexity bounds
for the above problem with three interpretations of
equivalent': as transition system isomorphism, as language
equivalence, and as bisimilarity. In particular, we solve two
problems left open in the literature. We also describe a logic
programming implementation which complements the existing
implementation for the synthesis of asynchronous automata initiated
by the second author.
| | format |
application/pdf
| | 332723 Bytes | |